package lc;

// import java.util.Arrays;

import org.junit.Test;

import util.BracketUtils;

public class Ex1289 {
    
    class Solution {
        public int minFallingPathSum(int[][] grid) {
            //只需要上一行的最小值和次小子
            //假设上一行的最小值下标为i，则f[x][i]需要的就是最小值，而其他位置都需要最小值
            int m = grid.length, n = grid[0].length;
            if (m == 1 && n == 1) {
                return grid[0][0];
            }
            int a = 0, b = 1, min = Integer.MAX_VALUE, ta, tb; //表示下标
            int[] f = new int[n];
            for (int i = m - 1; i >= 0; i--) {
                tb = f[b]; //次小值
                ta = f[a];
                int curMin = -1, curSend = -1;
                for (int j = 0; j < n; j++) {
                    if (j == a) {
                        //与上一行最小值同一列
                        f[j] = tb + grid[i][j];
                    // } else {
                        f[j] = ta + grid[i][j];
                    }
                    if (curMin < 0 || f[curMin] > f[j]) {
                        curSend = curMin;
                        curMin = j;
                    } else if (curSend < 0 || f[curSend] > f[j]) {
                        curSend = j;
                    }
                    if (i == 0) {
                        min = Math.min(min, f[j]);
                    }
                }
                a = curMin;
                b = curSend;
                // System.out.println(Arrays.toString(f));

            }
            return min;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[][] nums = BracketUtils.to2DArray("[[50,-18,-38,39,-20,-37,-61,72,22,79],[82,26,30,-96,-1,28,87,94,34,-89],[55,-50,20,76,-50,59,-58,85,83,-83],[39,65,-68,89,-62,-53,74,2,-70,-90],[1,57,-70,83,-91,-32,-13,49,-11,58],[-55,83,60,-12,-90,-37,-36,-27,-19,-6],[76,-53,78,90,70,62,-81,-94,-32,-57],[-32,-85,81,25,80,90,-24,10,27,-55],[39,54,39,34,-45,17,-2,-61,-81,85],[-77,65,76,92,21,68,78,-13,39,22]]");
        System.out.println(s.minFallingPathSum(nums));
    }

}
